home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 167_01 / mtp.c < prev    next >
Text File  |  1985-11-13  |  20KB  |  792 lines
  1. /* 
  2. HEADER:     CUG
  3. TITLE:        MTP.C - Macro Text Processor;
  4. VERSION:    0.05;
  5. DATE:        09/13/86;
  6. DESCRIPTION:    "MTP is a Macro Text Processor that performs
  7.         macro expansions of specified text patterns in
  8.         a file. Based on the deterministic finite state
  9.         automaton of UNIX's fgrep utility, it has the
  10.         distinction of not requiring a symbol table for
  11.         the list of macro expansions. The text patterns
  12.         are identified without backtracking, and need not
  13.         consist of one alphanumeric 'word' as with most
  14.         other macro processors.";
  15. KEYWORDS:    macro,text,fgrep,filter;
  16. SYSTEM:        ANY;
  17. FILENAME:    MTP.C;
  18. WARNINGS:    "As you can see from the version number, MTP is
  19.         very much in the developmental stage. This is not
  20.         to say it is bug-ridden. What is presented here
  21.         should be free of bugs. It does however have very
  22.         few options at present. These will be added in
  23.         future versions, based on user (yes - YOU!)
  24.         feedback. It is being released as an example of
  25.         what you can do with the Aho-Corasick algorithm
  26.         other than FGREP (see FGREP.DOC)";
  27. CRC:        xxxx
  28. SEE-ALSO:    FGREP.DOC,FGREP.C;
  29. AUTHORS:    Ian Ashdown - byHeart Software;
  30. COMPILERS:    ANY;
  31. REFERENCES:    ;
  32. ENDREF
  33. */
  34.  
  35. /*-------------------------------------------------------------*/
  36.  
  37. /* MTP.C - Macro Text Processor
  38.  *
  39.  * Version 0.05          September 13th, 1986
  40.  *
  41.  * Copyright 1986:    Ian Ashdown
  42.  *              byHeart Software
  43.  *              620 Ballantree Road
  44.  *              West Vancouver, B.C.
  45.  *              Canada V7S 1W3
  46.  *              (604) 922-6148
  47.  *
  48.  * This program may be copied for personal, non-commercial use
  49.  * only, provided that the above copyright notice is included in
  50.  * all copies of the source code. Copying for any other use
  51.  * without previously obtaining the written permission of the
  52.  * author is prohibited.
  53.  *
  54.  * Notes:
  55.  *
  56.  * The algorithm used in this program constructs a deterministic
  57.  * finite state automaton (FSA) for pattern matching from the sub-
  58.  * strings, then uses the FSA to process the text string in one
  59.  * pass. The time taken to construct the FSA is proportional to
  60.  * the sum of the lengths of the the substrings. The number of
  61.  * state transitions made by the FSA in processing the text
  62.  * string is independent of the number of substrings.
  63.  *
  64.  * Algorithm Source:
  65.  *
  66.  * "Efficient String Matching: An Aid to Bibliographic Search"
  67.  * Alfred V. Aho & Margaret J. Corasick
  68.  * Communications of the ACM
  69.  * pp. 333 - 340, Vol. 18 No. 6 (June '75)
  70.  *
  71.  * USAGE: mtp [-n] string_file <files>
  72.  *
  73.  * where:
  74.  *
  75.  *    -n    Substitutions are not nested. That is, once a
  76.  *        translation string has been substituted for a
  77.  *        source string, the substitution itself is not
  78.  *        scanned for another string to substitute.
  79.  *
  80.  *    string_file
  81.  *
  82.  *        is a text file of newline-separated
  83.  *        source-translation strings. Each line of the file
  84.  *        comprises one string, and consists of a source
  85.  *        string, followed by one or more '\t' (tab)
  86.  *        characters, and a translation string. Source
  87.  *        strings may not contain '\t' or '\0' (NULL)
  88.  *        characters. Translation strings may not contain
  89.  *        '\0' characters. Empty lines consisting of only a
  90.  *        newline ('\n') are permitted. Example:
  91.  *
  92.  *        Replace me\twith me!
  93.  *
  94.  *    file    is any text file consisting of newline-separated
  95.  *        strings.
  96.  *
  97.  * DIAGNOSTICS:
  98.  *
  99.  * Exit status is 0 unless error was encountered, in which case
  100.  * an exit status of 2 is returned.
  101.  *
  102.  * BUGS:  Lines are limited to 256 characters.
  103.  */
  104.  
  105. /*** Include Files ***/
  106.  
  107. #include <stdio.h>
  108. #include <ctype.h>
  109.  
  110. /*** Definitions ***/
  111.  
  112. #define TRUE           1
  113. #define FALSE           0
  114. #define MAX_LINE     257  /* Maximum number of characters */
  115.                   /* per line plus NULL delimiter */
  116.  
  117. /* The following definition applies to the Lattice C compiler
  118.  * (Version 2.15) for MS-DOS. The Lattice library does not have
  119.  * the Unix function "index()". However, it does have an
  120.  * equivalent function called "stpchr()".
  121.  */
  122.  
  123. /* #define index stpchr */    /* Remove comment delimiters for */
  124.                   /* Lattice C version 2.15 */
  125.  
  126. #define CMD_ERR       0    /* Error codes */
  127. #define OPT_ERR       1
  128. #define INP_ERR       2
  129. #define STR_ERR       3
  130. #define MEM_ERR       4
  131.  
  132. /*** Typedefs ***/
  133.  
  134. typedef int BOOL;    /* Boolean flag */
  135.  
  136. /* Some C compilers, including Lattice C, do not support the
  137.  * "void" data type. Remove the following comment delimiters for
  138.  * such compilers.
  139.  */
  140.  
  141. /* typedef int void; */
  142.  
  143. /*** Data Structures ***/
  144.  
  145. /* Queue element */
  146.  
  147. typedef struct queue
  148. {
  149.   struct state_el *st_ptr;
  150.   struct queue *next_el;
  151. } QUEUE;
  152.  
  153. /* Transition element */
  154.  
  155. typedef struct transition
  156. {
  157.   char lchar;            /* Transition character */
  158.   struct state_el *nextst_ptr;    /* Transition state pointer */
  159.   struct transition *next_el;
  160. } TRANSITION;
  161.  
  162. /* FSA state element */
  163.  
  164. typedef struct state_el
  165. {
  166.   TRANSITION *go_ls;    /* Pointer to head of "go" list */
  167.   TRANSITION *mv_ls;    /* Pointer to head of "move" list */
  168.   struct state_el *fail_state;    /* "failure" transition state */
  169.   char *out_str;    /* Terminal state message (if any) */
  170.   int src_length;    /* Source substring length */
  171.   int trn_length;    /* Translation substring length */
  172. } FSA;
  173.  
  174. /*** Global Variables and Structures ***/
  175.  
  176. /* Dummy "failure" state */
  177.  
  178. FSA FAIL_STATE;
  179.  
  180. /* Define a separate data structure for State 0 of the FSA to
  181.  * speed processing of the input while the FSA is in that state.
  182.  * Since the Aho-Corasick algorithm only defines "go" transitions
  183.  * for this state (one for each valid input character) and no
  184.  * "failure" transitions or output messages, only an array of
  185.  * "go" transition state numbers is needed. The array is accessed
  186.  * directly, using the input character as the index.
  187.  */
  188.  
  189. FSA *MZ[128];    /* State 0 of FSA */
  190.  
  191. /* Command-line option flags */
  192.  
  193. BOOL nflag = FALSE;  /* Substitution nesting disabled if TRUE */
  194.  
  195. /*** Main Body of Program ***/
  196.  
  197. int main(argc,argv)
  198. int argc;
  199. char **argv;
  200. {
  201.   char *temp;
  202.   void proc_file(),
  203.        bd_go(),
  204.        bd_move(),
  205.        error();
  206.  
  207.   /* Check for minimum number of command line arguments */
  208.  
  209.   if(argc < 2)
  210.     error(CMD_ERR,NULL);
  211.  
  212.   /* Parse the command line for user-selected options */
  213.  
  214.   while(--argc && (*++argv)[0] == '-')
  215.     for(temp = argv[0]+1; *temp != '\0'; temp++)    
  216.       switch(toupper(*temp))
  217.       {
  218.     case 'N':
  219.       nflag = TRUE;
  220.       break;
  221.     default:
  222.       error(OPT_ERR,NULL);
  223.       }
  224.  
  225.   /* Check for string file argument */
  226.  
  227.   if(!argc)
  228.     error(CMD_ERR,NULL);
  229.  
  230.   /* Build the "go" transitions. */
  231.  
  232.   bd_go(*argv++);
  233.   argc--;
  234.  
  235.   /* Build the "failure" and "move" transitions */
  236.  
  237.   bd_move();
  238.  
  239.   /* Process each of the input files if not "stdin". */
  240.  
  241.   if(!argc)
  242.     proc_file(NULL);
  243.   else
  244.     while(argc--)
  245.       proc_file(*argv++);
  246.  
  247.   /* Return 0 to the parent process to indicate no errors. */
  248.  
  249.   exit(0);
  250. }
  251.  
  252. /*** Functions and Procedures ***/
  253.  
  254. /* PROC_FILE() - Run the FSA on the input file "in_file" */
  255.  
  256. void proc_file(in_file)
  257. char *in_file;
  258. {
  259.   char buffer[2*MAX_LINE],    /* Input string buffer */
  260.        *nl,
  261.        *index(),
  262.        *fgets();
  263.   FILE *in_fd,
  264.        *fopen();
  265.   void run_fsa(),
  266.        error();
  267.  
  268.   if(in_file != NULL)    /* A file was specified as the input */
  269.   {
  270.     if(!(in_fd = fopen(in_file,"r")))
  271.       error(INP_ERR,in_file);
  272.   }
  273.   else
  274.     in_fd = stdin;
  275.  
  276.   /* Read in a line at a time for processing */
  277.  
  278.   while(fgets(buffer,MAX_LINE,in_fd))
  279.   {
  280.     if(nl = index(buffer,'\n'))  /* Remove newline */
  281.       *nl = '\0';
  282.     run_fsa(buffer);    /* Run the FSA on string "buffer" */
  283.     puts(buffer);    /* Output the translated string */
  284.   }
  285.   if(in_file != NULL)
  286.     fclose(in_fd);
  287. }
  288.  
  289. /* RUN_FSA() - Run the finite state automaton with string
  290.  *           "target" as input.
  291.  */
  292.  
  293. void run_fsa(target)
  294. register char *target;
  295. {
  296.   register FSA *st_ptr;
  297.   char tail[MAX_LINE];
  298.   FSA *go(),
  299.       *move();
  300.  
  301.   st_ptr = NULL;    /* Initialize FSA */
  302.  
  303.   /* Process the next input character in the target string */
  304.  
  305.   while(*target)
  306.   {
  307.     st_ptr = move(st_ptr,*target);
  308.  
  309.     /* Substitute translation string for sou